SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Consensus based optimization</title>

</head>

Consensus based optimization

</h1>

</header>

Consensus-based optimization (CBO)<a href="#cite_note-:0-1">[1]</a> is a multi-agent <a href="Derivative-free_optimization" title="Derivative-free optimization">derivative-free optimization</a> method, designed to obtain solutions for global optimization problems of the form <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min _{x\in {\cal {X}}}f(x),}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{x\in {\cal {X}}}f(x),}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:{\mathcal {X}}\to \mathbb {R} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:{\mathcal {X}}\to \mathbb {R} }</annotation>

</semantics>

</math><img src="./402b00d0d97866a1471384e267d1bcab70bb23ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.383ex; height:2.509ex;" alt="{\displaystyle f:{\mathcal {X}}\to \mathbb {R} }" loading="lazy"> denotes the objective function acting on the state space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\cal {X}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\cal {X}}}</annotation>

</semantics>

</math><img src="./665536ed9698be58cd8bacaf30a527aa0be1649a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.875ex; height:2.176ex;" alt="{\displaystyle {\cal {X}}}" loading="lazy">, which is assumed to be a <a href="Normed_vector_space" title="Normed vector space">normed vector space</a>. The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> can potentially be nonconvex and nonsmooth. The algorithm employs particles or agents to explore the state space, which communicate with each other to update their positions. Their dynamics follows the paradigm of <a href="Metaheuristic" title="Metaheuristic">metaheuristics</a>, which blend exporation with exploitation. In this sense, CBO is comparable to <a href="Ant_colony_optimization_algorithms" title="Ant colony optimization algorithms">ant colony optimization</a>, wind driven optimization,<a href="#cite_note-2">[2]</a> <a href="Particle_swarm_optimization" title="Particle swarm optimization">particle swarm optimization</a> or <a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a>.

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

Consider an ensemble of points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=(x_{t}^{1},\dots ,x_{t}^{N})\in {\cal {X}}^{N}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}=(x_{t}^{1},\dots ,x_{t}^{N})\in {\cal {X}}^{N}}</annotation>

</semantics>

</math><img src="./51ccd3e977a1950ba580d51c701711989c46f503.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.12ex; height:3.343ex;" alt="{\displaystyle x_{t}=(x_{t}^{1},\dots ,x_{t}^{N})\in {\cal {X}}^{N}}" loading="lazy">, dependent of the time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in [0,\infty )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in [0,\infty )}</annotation>

</semantics>

</math><img src="./505b13e7abab4425756bd9fd4367d8f9be2ac1fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.752ex; height:2.843ex;" alt="{\displaystyle t\in [0,\infty )}" loading="lazy">. Then the update for the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th particle is formulated as a stochastic differential equation,

</mrow>

</mrow>

</msubsup>

<mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

<mtext>consensus drift</mtext>

</mrow>

</munder>

<mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</munder>

</mrow>

<mtext>scaled diffusion</mtext>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx_{t}^{i}=-\lambda \,\underbrace {(x_{t}^{i}-c_{\alpha }(x_{t}))\,dt} _{\text{consensus drift}}+\sigma \underbrace {D(x_{t}^{i}-c_{\alpha }(x_{t}))\,dB_{t}^{i}} _{\text{scaled diffusion}},}</annotation>

</semantics>

</math><img src="./c5f3c5f14b5e917ff3cdf37eb4734817e4c6c8ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.338ex; width:49.52ex; height:6.509ex;" alt="{\displaystyle dx_{t}^{i}=-\lambda \,\underbrace {(x_{t}^{i}-c_{\alpha }(x_{t}))\,dt} _{\text{consensus drift}}+\sigma \underbrace {D(x_{t}^{i}-c_{\alpha }(x_{t}))\,dB_{t}^{i}} _{\text{scaled diffusion}},}" loading="lazy">

with the following components:

<ul><li>The consensus point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{\alpha }(x)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{\alpha }(x)}</annotation>

</semantics>

</math><img src="./0b01c1ab9813496942ea047dc8d9023f933a6766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.43ex; height:2.843ex;" alt="{\displaystyle c_{\alpha }(x)}" loading="lazy">: The key idea of CBO is that in each step the particles “agree” on a common consensus point, by computing an average of their positions, weighted by their current objective function value <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{\alpha }(x_{t})={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }(x_{t}^{i})}}\sum _{i=1}^{N}x_{t}^{i}\ \omega _{\alpha }(x_{t}^{i}),\quad {\text{ with }}\quad \omega _{\alpha }(\,\cdot \,)=\mathrm {exp} (-\alpha f(\,\cdot \,)).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{\alpha }(x_{t})={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }(x_{t}^{i})}}\sum _{i=1}^{N}x_{t}^{i}\ \omega _{\alpha }(x_{t}^{i}),\quad {\text{ with }}\quad \omega _{\alpha }(\,\cdot \,)=\mathrm {exp} (-\alpha f(\,\cdot \,)).}</annotation>

</semantics>

</math>This point is then used in the drift term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}^{i}-c_{\alpha }(x_{t})}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}^{i}-c_{\alpha }(x_{t})}</annotation>

</semantics>

</math><img src="./c123982241964819e59996d25bd0bbddec81489c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.252ex; height:3.176ex;" alt="{\displaystyle x_{t}^{i}-c_{\alpha }(x_{t})}" loading="lazy">, which moves each particle into the direction of the consensus point.</li>

<li>Scaled noise: For each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\geq 0}</annotation>

</semantics>

</math><img src="./248525429e9cd266f53ab8c52d17bc206c546060.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.101ex; height:2.343ex;" alt="{\displaystyle t\geq 0}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\dots ,N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\dots ,N}</annotation>

</semantics>

</math><img src="./2537dcf59e68022de4f253dbadbd152c9d3eec47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.305ex; height:2.509ex;" alt="{\displaystyle i=1,\dots ,N}" loading="lazy">, we denote by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{t}^{i}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{t}^{i}}</annotation>

</semantics>

</math><img src="./312484ea77001c0e9cae8dd902fc7dc5fcce68d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.59ex; height:3.176ex;" alt="{\displaystyle B_{t}^{i}}" loading="lazy"> independent standard Brownian motions. The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D:{\cal {X}}\to \mathbb {R} ^{s}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D:{\cal {X}}\to \mathbb {R} ^{s}}</annotation>

</semantics>

</math><img src="./0e768aa9804d8f11823367dc616704e0077a99c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.032ex; height:2.343ex;" alt="{\displaystyle D:{\cal {X}}\to \mathbb {R} ^{s}}" loading="lazy"> incorporates the drift of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th particle and determines the noise model. The most common choices are:

<ul><li>Isotropic noise, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(\cdot )=\|\cdot \|}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(\cdot )=\|\cdot \|}</annotation>

</semantics>

</math><img src="./89fe5f485e99e2c0aa47371a00873c9d0981ddc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.483ex; height:2.843ex;" alt="{\displaystyle D(\cdot )=\|\cdot \|}" loading="lazy">: In this case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=1}</annotation>

</semantics>

</math><img src="./bac386d8f227fb823cede9b3e33d706cad3ed306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=1}" loading="lazy"> and every component of the noise vector is scaled equally. This was used in the original version of the algorithm.<a href="#cite_note-:0-1">[1]</a></li>

<li>Anisotropic noise<a href="#cite_note-3">[3]</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(\cdot )=|\cdot |}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(\cdot )=|\cdot |}</annotation>

</semantics>

</math><img src="./ab87a9aac4d3e180e9fef7c68a202ab0cca8bf39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.452ex; height:2.843ex;" alt="{\displaystyle D(\cdot )=|\cdot |}" loading="lazy">: In the special case, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\cal {X}}\subset \mathbb {R} ^{d}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\cal {X}}\subset \mathbb {R} ^{d}}</annotation>

</semantics>

</math><img src="./e6b05219a578665ffbe085e4ff18e4cb354a85c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.744ex; height:2.676ex;" alt="{\displaystyle {\cal {X}}\subset \mathbb {R} ^{d}}" loading="lazy">, this means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=d}</annotation>

</semantics>

</math><img src="./040513350f36d458b76d1c040cc9e825597f48a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.405ex; height:2.176ex;" alt="{\displaystyle s=d}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> applies the absolute value function component-wise. Here, every component of the noise vector is scaled, dependent on the corresponding entry of the drift vector.</li></ul></li>

<li>Hyperparameters: The parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma \geq 0}</annotation>

</semantics>

</math><img src="./484c025204c6e6189248ac64a254dd2f7c3ff4f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle \sigma \geq 0}" loading="lazy"> scales the influence of the noise term. The parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha \geq 0}</annotation>

</semantics>

</math><img src="./d9e01f6a4360f062e662779cb235d41c7c68a557.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.749ex; height:2.343ex;" alt="{\displaystyle \alpha \geq 0}" loading="lazy"> determines the separation effect of the particles:<a href="#cite_note-:0-1">[1]</a>

<ul><li>in the limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \to 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha \to 0}</annotation>

</semantics>

</math><img src="./8301a73b99f64316603b480253ad2cd4cdd87681.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.264ex; height:2.176ex;" alt="{\displaystyle \alpha \to 0}" loading="lazy"> every particle is assigned the same weight and the consensus point is a regular mean.</li>

<li>In the limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \to \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha \to \infty }</annotation>

</semantics>

</math><img src="./1488b56a327cc223bac1548a520344c56552abf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.425ex; height:1.843ex;" alt="{\displaystyle \alpha \to \infty }" loading="lazy"> the consensus point corresponds to the particle with the best objective value, completely ignoring the position of other points in the ensemble.</li></ul></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Implementation_notes">Implementation notes</h2></div>

In practice, the SDE is discretized via the <a href="Euler%E2%80%93Maruyama_method" title="Euler–Maruyama method">Euler–Maruyama method</a> such that the following explicit update formula for the ensemble <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=(x^{1},\dots ,x^{N})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=(x^{1},\dots ,x^{N})}</annotation>

</semantics>

</math><img src="./ff1a08817934044e6ee10c994141214e66b415f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.821ex; height:3.176ex;" alt="{\displaystyle x=(x^{1},\dots ,x^{N})}" loading="lazy"> is obtained,<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{i}\gets x^{i}-\lambda \,(x^{i}-c_{\alpha }(x))\,dt+\sigma D(x^{i}-c_{\alpha }(x))\,B^{i}.}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{i}\gets x^{i}-\lambda \,(x^{i}-c_{\alpha }(x))\,dt+\sigma D(x^{i}-c_{\alpha }(x))\,B^{i}.}</annotation>

</semantics>

</math>If one can employ an efficient implementation of the <a href="LogSumExp" title="LogSumExp">LogSumExp</a> functions, this can be beneficial for numerical stability of the consensus point computation. We refer to existing implementation in <a href="Python_(programming_language)" title="Python (programming language)">Python</a> <a rel="nofollow" class="external autonumber" href="https://pdips.github.io/CBXpy/">[1]</a> and <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a> <a rel="nofollow" class="external autonumber" href="https://github.com/PdIPS/CBX.jl">[2]</a>.

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sampling">Sampling</h3></div>

Consensus-based optimization can be transformed into a sampling method<a href="#cite_note-4">[4]</a> by modifying the noise term and choosing appropriate hyperparameters. Namely, one considers the following SDE

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msqrt>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx_{t}^{i}=-(x_{t}^{i}-c_{\alpha }(x_{t}))\,dt+{\sqrt {2{\tilde {\lambda }}^{-1}\,C_{\alpha }(x_{t})}}\,dB_{t}^{i},}</annotation>

</semantics>

</math><img src="./ccbfbb308abc249d5137dbcd75544fbc1a242878.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:45.934ex; height:4.843ex;" alt="{\displaystyle dx_{t}^{i}=-(x_{t}^{i}-c_{\alpha }(x_{t}))\,dt+{\sqrt {2{\tilde {\lambda }}^{-1}\,C_{\alpha }(x_{t})}}\,dB_{t}^{i},}" loading="lazy">

where the weighted covariance matrix is defined as

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\alpha }(x_{t}):={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }(x_{t}^{i})}}\sum _{i=1}^{N}(x_{t}^{i}-c(x_{t}))\otimes (x_{t}^{i}-c(x_{t}))\omega (x_{t}^{i})}</annotation>

</semantics>

</math><img src="./ddd47b41ae147217fd45a3e92d686c184627a77c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:59.476ex; height:7.509ex;" alt="{\displaystyle C_{\alpha }(x_{t}):={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }(x_{t}^{i})}}\sum _{i=1}^{N}(x_{t}^{i}-c(x_{t}))\otimes (x_{t}^{i}-c(x_{t}))\omega (x_{t}^{i})}" loading="lazy">.

If the parameters are chosen such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {\lambda }}^{-1}=(1+\alpha )}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {\lambda }}^{-1}=(1+\alpha )}</annotation>

</semantics>

</math><img src="./a8e31ae21c577f8ff60080b4f33d653f89f75ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.086ex; height:3.676ex;" alt="{\displaystyle {\tilde {\lambda }}^{-1}=(1+\alpha )}" loading="lazy"> the above scheme creates approximate samples of a probability distribution with a density, that is proportional to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \exp(-\alpha f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \exp(-\alpha f)}</annotation>

</semantics>

</math><img src="./efb512ff5e927337ac2544207d056e4db66249eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.936ex; height:2.843ex;" alt="{\displaystyle \exp(-\alpha f)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Polarization">Polarization</h3></div>

If the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is multi-modal, i.e., has more than one global minimum, the standard CBO algorithm can only find one of these points. However, one can “polarize”<a href="#cite_note-5">[5]</a> the consensus computation by introducing a kernel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k:{\cal {{X}\times {\cal {{X}\to [0,\infty )}}}}}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k:{\cal {{X}\times {\cal {{X}\to [0,\infty )}}}}}</annotation>

</semantics>

</math><img src="./066c391e08f16add8069825013033fa03df2fa8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.425ex; height:2.843ex;" alt="{\displaystyle k:{\cal {{X}\times {\cal {{X}\to [0,\infty )}}}}}" loading="lazy"> that includes local information into the weighting. In this case, every particle has its own version of the consensus point, which is computed as<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{\alpha }^{j}(x)={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }^{j}(x^{i})}}\sum _{i=1}^{N}x^{i}\ \omega _{\alpha }^{j}(x^{i}),\quad {\text{ with }}\quad \omega _{\alpha }^{j}(\,\cdot \,)=\mathrm {exp} (-\alpha f(\,\cdot \,))\,k(\cdot ,x^{j}).}">

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{\alpha }^{j}(x)={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }^{j}(x^{i})}}\sum _{i=1}^{N}x^{i}\ \omega _{\alpha }^{j}(x^{i}),\quad {\text{ with }}\quad \omega _{\alpha }^{j}(\,\cdot \,)=\mathrm {exp} (-\alpha f(\,\cdot \,))\,k(\cdot ,x^{j}).}</annotation>

</semantics>

</math>In this case, the drift is a vector field over the state space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\cal {X}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\cal {X}}}</annotation>

</semantics>

</math><img src="./665536ed9698be58cd8bacaf30a527aa0be1649a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.875ex; height:2.176ex;" alt="{\displaystyle {\cal {X}}}" loading="lazy">. Intuitively, particles are now not only attracted to other particles based on their objective value, but also based on their spatial locality. For a constant kernel function, the polarized version corresponds to standard CBO and is therefore a generalization. We briefly give some examples of common configurations:

<ul><li>Gaussian kernel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k(\cdot ,\cdot )=\exp \left(-{\frac {1}{2\kappa ^{2}\alpha }}\|\cdot -\cdot \|_{2}^{2}\right)}">

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k(\cdot ,\cdot )=\exp \left(-{\frac {1}{2\kappa ^{2}\alpha }}\|\cdot -\cdot \|_{2}^{2}\right)}</annotation>

</semantics>

</math><img src="./a562cf8e654f750f6424efb610fb5c2962bb0460.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:31.653ex; height:6.176ex;" alt="{\displaystyle k(\cdot ,\cdot )=\exp \left(-{\frac {1}{2\kappa ^{2}\alpha }}\|\cdot -\cdot \|_{2}^{2}\right)}" loading="lazy">: the parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \kappa }</annotation>

</semantics>

</math><img src="./54ddec2e922c5caea4e47d04feef86e782dc8e6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:1.676ex;" alt="{\displaystyle \kappa }" loading="lazy"> determines the communication radius of particles. This choice corresponds to a local convex regularization of the objective function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">.</li>

<li><a href="Mean-shift_algorithm" class="mw-redirect" title="Mean-shift algorithm">Mean-shift algorithm</a>:<a href="#cite_note-6">[6]</a> Employing polarized CBO for a constant objective function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, together with no noise (i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma =0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma =0}</annotation>

</semantics>

</math><img src="./1eb4831f1e0ca1ba7d007dc6b973e54787e1a4b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.591ex; height:2.176ex;" alt="{\displaystyle \sigma =0}" loading="lazy">) and an Euler–Maruyama discretization with step size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dt=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dt=1}</annotation>

</semantics>

</math><img src="./a1ec14460ac34b4e2d2ed8cb672cb9571fd79295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.316ex; height:2.176ex;" alt="{\displaystyle dt=1}" loading="lazy">, corresponds to the mean-shift algorithm.</li>

<li>Bounded confidence model: When choosing a constant objective function, no noise model, but also the special kernel function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k(x,{\tilde {x}})=1_{\|x-{\tilde {x}}\|\leq \kappa }}">

<mover>

</mover>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k(x,{\tilde {x}})=1_{\|x-{\tilde {x}}\|\leq \kappa }}</annotation>

</semantics>

</math><img src="./c46e6c6f140c1a2958dc22f1331bbd6abdc515e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:18.241ex; height:3.343ex;" alt="{\displaystyle k(x,{\tilde {x}})=1_{\|x-{\tilde {x}}\|\leq \kappa }}" loading="lazy">, the SDE in transforms to a ODE known as the bounded confidence model,<a href="#cite_note-7">[7]</a> which arises in opinion dynamics.</li></ul>

<ul><li><a href="Particle_Swarm_Optimization" class="mw-redirect" title="Particle Swarm Optimization">Particle Swarm Optimization</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Ant_colony_optimization_algorithms" title="Ant colony optimization algorithms">Ant colony optimization algorithms</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFPinnauTotzeckTseMartin2017" class="citation journal cs1">Pinnau, René; Totzeck, Claudia; Tse, Oliver; Martin, Stephan (January 2017). <a rel="nofollow" class="external text" href="https://www.worldscientific.com/doi/abs/10.1142/S0218202517400061">"A consensus-based model for global optimization and its mean-field limit"</a>. Mathematical Models and Methods in Applied Sciences. 27 (1): 183–204. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1604.05648">1604.05648</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0218202517400061">10.1142/S0218202517400061</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0218-2025">0218-2025</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119296432">119296432</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFBayraktarKomurcuBossardWerner2013" class="citation journal cs1">Bayraktar, Zikri; Komurcu, Muge; Bossard, Jeremy A.; Werner, Douglas H. (2013). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/6407788">"The Wind Driven Optimization Technique and its Application in Electromagnetics"</a>. IEEE Transactions on Antennas and Propagation. 61 (5): 2745–2757. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013ITAP...61.2745B">2013ITAP...61.2745B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTAP.2013.2238654">10.1109/TAP.2013.2238654</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:38181295">38181295</a>. Retrieved 2024-02-03.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFCarrilloJinLiZhu2020" class="citation arxiv cs1">Carrillo, José A.; Jin, Shi; Li, Lei; Zhu, Yuhua (2020-03-04). "A consensus-based global optimization method for high dimensional machine learning problems". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1909.09249">1909.09249</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.OC">math.OC</a>].</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFCarrilloHoffmannStuartVaes2021" class="citation cs2">Carrillo, J. A.; Hoffmann, F.; Stuart, A. M.; Vaes, U. (2021-11-04), Consensus Based Sampling, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2106.02519">2106.02519</a></cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBungertRoithWacker2023" class="citation arxiv cs1">Bungert, Leon; Roith, Tim; Wacker, Philipp (2023-10-09). "Polarized consensus-based dynamics for optimization and sampling". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2211.05238">2211.05238</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.OC">math.OC</a>].</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFFukunagaHostetler1975" class="citation journal cs1">Fukunaga, K.; Hostetler, L. (January 1975). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/1055330">"The estimation of the gradient of a density function, with applications in pattern recognition"</a>. IEEE Transactions on Information Theory. 21 (1): 32–40. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1975.1055330">10.1109/TIT.1975.1055330</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0018-9448">0018-9448</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFDeffuantNeauAmblardWeisbuch2000" class="citation journal cs1">Deffuant, Guillaume; Neau, David; Amblard, Frederic; Weisbuch, Gérard (January 2000). <a rel="nofollow" class="external text" href="https://www.worldscientific.com/doi/abs/10.1142/S0219525900000078">"Mixing beliefs among interacting agents"</a>. Advances in Complex Systems. 03 (1n04): 87–98. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0219525900000078">10.1142/S0219525900000078</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0219-5259">0219-5259</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15604530">15604530</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-26" href="https://en.wikipedia.org/wiki/?title=Consensus_based_optimization&oldid=1292435473">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>